// Copyright 2011, Vanya Davidenko.
// Кодировка файла: UTF-8. 
package info.iu9.red;

import info.iu9.interval_tree.IntInterval;
import info.iu9.interval_tree.IntervalSearchSet;
import info.iu9.interval_tree.IntervalTree;

import java.util.Arrays;
import java.util.BitSet;



interface State {
  void accept(final StateVisitor v);
}

// Состояние-команда, содержит единственный epsilon-переход
// (в другое состояние или вникуда).
interface CommandState extends State {}

// Состояние, перед переходом по которому интерпретатор проверяет выполнение
// некоторого условия (например, якоря). Каждый якорь должен выполнять
// требования своего базового класса и возможно некоторые дополнительные.
interface AnchorState extends CommandState {
  boolean check(final StringPosition s);
}

// Обычное состояние, содержит переходы по символам.
interface RegularState extends State {
  boolean check(final StringPosition s);
}



// Успешный результат поиска.
class MatchState implements CommandState {
  public void accept(final StateVisitor v) { v.visit(this); }
}



// Сохранение текущей позиции.
abstract class SaveState implements CommandState {
  SaveState(final int submatch_num) { submatch_num_ = submatch_num; }
  public int submatch_num() { return submatch_num_; }
  private final int submatch_num_;
}

class BeginSaveState extends SaveState {
  BeginSaveState(final int submatch_num) { super(submatch_num); }
  public void accept(final StateVisitor v) { v.visit(this); }
}

class EndSaveState extends SaveState {
  EndSaveState(final int submatch_num) { super(submatch_num); }
  public void accept(final StateVisitor v) { v.visit(this); }
}



// Безусловный переход в заданной методом next() состояние.
class JumpState implements CommandState {
  JumpState(final int next) { next_ = next; }
  public void accept(final StateVisitor v) { v.visit(this); }
  public int next() { return next_; }
  private final int next_;
}

// Развилка, с двумя эпсилон-переходами.
// Состояние next() должно обрабатываться раньше, чем next_low().
class ForkState implements CommandState {
  ForkState(final int next, final int next_low) {
    next_ = next;
    next_low_ = next_low;
  }
  public void accept(final StateVisitor v) { v.visit(this); }
  public int next() { return next_; }
  public int next_low() { return next_low_; }

  private final int next_;
  private final int next_low_;
}



// '^' в режиме singleline: начало строки.
class BeginningAnchorState implements AnchorState {
  public void accept(final StateVisitor v) { v.visit(this); }
  public boolean check(final StringPosition s) { return s.isStringBegin(); }
}

// '\z': конец строки (за последним символом).
class EndOfStringAnchorState implements AnchorState {
  public void accept(final StateVisitor v) { v.visit(this); }
  public boolean check(final StringPosition s) { return s.isStringEnd(); }
}

// '$' в режиме singleline: конец строки или \n последним символом.
class EndingAnchorState extends EndOfStringAnchorState {
  public void accept(final StateVisitor v) { v.visit(this); }
  public boolean check(final StringPosition s) {
    return super.check(s) || s.getCurrent() == '\n' && s.getNext() == s.EOL;
  }
}

// Специальное состояние, используемое только при построение обратного автомата.
// $ в режиме singleline: конец строки или \n последним символом,
// обратного для него якоря: начало строки или \n нулевым символом.
// Данный якорь является простейшим решением данной проблемы, хаком :-)
class ReverseEndingAnchorState implements AnchorState {
  public void accept(final StateVisitor v) { v.visit(this); }
  public boolean check(final StringPosition s) {
    return s.isStringBegin() || s.getPrev() == '\n' && s.getPrevPrev() == s.EOL;
  }
}

// Соответствует '\A': начало стоки.
// То же самое, что и BeginningAnchorState, только другая метка состояния.
class StringBeginningAnchorState extends BeginningAnchorState {
  public void accept(final StateVisitor v) { v.visit(this); }
}

// Соответствует '\Z': конец строки или \n предпоследним символом.
// То же самое, что и EndingAnchorState, только другая метка состояния.
class StringEndingAnchorState extends EndingAnchorState {
  public void accept(final StateVisitor v) { v.visit(this); }
}

// '^' в режиме multiline: '^' в singleline или после '\n'.
class MultiLineBeginningAnchorState extends BeginningAnchorState {
  public void accept(final StateVisitor v) { v.visit(this); }
  public boolean check(final StringPosition s) {
    return super.check(s) || s.getPrev() == '\n';
  }
}

// '$' в режиме multiline: '$' в singleline или перед '\n'.
class MultiLineEndingAnchorState extends EndingAnchorState {
  public void accept(final StateVisitor v) { v.visit(this); }
  public boolean check(final StringPosition s) {
    return super.check(s) || s.getCurrent() == '\n';
  }
}


class BaseWordBoundaryAnchorState {
  protected boolean isWordCharacter(final int c) {
    return word_char_set_.contains(c);
  }
  static {
    final IntervalTree t = new IntervalTree();
    t.insert(new IntInterval('a', 'z'));
    t.insert(new IntInterval('A', 'Z'));
    t.insert(new IntInterval('0', '9'));
    t.insert(new IntInterval('_', '_'));
    word_char_set_ = t.compile();
  }
  private static final IntervalSearchSet word_char_set_;
}

// \b-якорь: текущий символ находится на границе слова.
class WordBoundaryAnchorState extends BaseWordBoundaryAnchorState
                              implements AnchorState {
  public void accept(final StateVisitor v) { v.visit(this); }
  public boolean check(final StringPosition s) {
    return isWordCharacter(s.getPrev()) != isWordCharacter(s.getCurrent());
  }
}

// \B-якорь: текущий символ не находится на границе слова.
class InvertedWordBoundaryAnchorState extends BaseWordBoundaryAnchorState
                                      implements AnchorState  {
  public void accept(final StateVisitor v) { v.visit(this); }
  public boolean check(final StringPosition s) {
    return isWordCharacter(s.getPrev()) == isWordCharacter(s.getCurrent());
  }
}



// Переход по любому символу кроме \n.
class DotState implements RegularState {
  public void accept(final StateVisitor v) { v.visit(this); }
  public boolean check(final StringPosition s) { return s.getCurrent()!= '\n'; }
}

// Переход по любому символу включая \n.
class DotAllState implements RegularState {
  public void accept(final StateVisitor v) { v.visit(this); }
  public boolean check(final StringPosition s) { return true; }
}


// Переход только по 1 символу.
class CharacterState implements RegularState {
  CharacterState(final int character) { character_ =  character; }
  public void accept(final StateVisitor v) { v.visit(this); }
  public boolean check(final StringPosition s) {
    return s.getCurrent() == character_;
  }
  public String toString() {
    final StringBuilder sb = new StringBuilder(1);
    sb.appendCodePoint(character_);
    return sb.toString();
  }
  int[] allCharacters() {
    final int[] result = new int[1];
    result[0] = character_;
    return result;
  }
  private final int character_;
}

// Переход только по 1 символу без учета его регистра.
class CaseCharacterState implements RegularState {
  CaseCharacterState(final int character) {
    lower_character_ = Character.toLowerCase(character);
  }
  public void accept(final StateVisitor v) { v.visit(this); }
  public boolean check(final StringPosition s) {
    return Character.toLowerCase(s.getCurrent()) == lower_character_;
  }
  public String toString() {
    final StringBuilder sb = new StringBuilder(1);
    sb.appendCodePoint(lower_character_);
    sb.appendCodePoint(Character.toUpperCase(lower_character_));
    return sb.toString();
  }
  int[] allCharacters() {
    final int[] result = new int[2];
    result[0] = lower_character_;
    result[1] = Character.toUpperCase(lower_character_);
    return result;
  }
  private final int lower_character_;
}


// Переход при принадлежности текущего символа множеству заданных.
class CharacterGroupState implements RegularState {
  CharacterGroupState(final IntervalSearchSet interval_set) {
    interval_set_ = interval_set;
  }
  public void accept(final StateVisitor v) { v.visit(this); }
  public boolean check(final StringPosition s) {
    return interval_set_.contains(s.getCurrent());
  }
  public String toString() {
    return interval_set_.toUnicodeCharSequenceString();
  }
  int[] allCharacters() {
    int size = 0;
    for ( final Integer i : interval_set_ ) {
      size++;
    }
    final int[] result = new int[size];
    int index = 0;
    for ( final Integer i : interval_set_ ) {
      result[index++] = i;
    }
    return result;
  }
  private final IntervalSearchSet interval_set_;
}

// Переход при принадлежности текущего символа множеству заданных
// без учета регистра.
class CaseCharacterGroupState implements RegularState {
  CaseCharacterGroupState(final IntervalSearchSet interval_set) {
    interval_set_ = interval_set;
  }
  public void accept(final StateVisitor v) { v.visit(this); }
  public boolean check(final StringPosition s) {
    final int l = Character.toLowerCase(s.getCurrent());
    final int u = Character.toLowerCase(s.getCurrent());
    return interval_set_.contains(l) || interval_set_.contains(u);
  }
  public String toString() {
    final StringBuilder sb = new StringBuilder();
    sb.append("CI: ");
    sb.append(interval_set_.toUnicodeCharSequenceString());
    return sb.toString();
  }
  int[] allCharacters() {
    int size = 0;
    for ( final Integer i : interval_set_ ) {
      size++;
    }

    final int[] max_result = new int[size * 2];

    final BitSet bs = new BitSet(0x10FFFF+ 1);
    int index = 0;
    for ( final Integer i : interval_set_ ) {
      final int lower = Character.toLowerCase(i);
      final int upper = Character.toUpperCase(i);

      if ( !bs.get(lower) ) {
        max_result[index++] = lower;
        bs.set(lower);
      }

      if ( !bs.get(upper) ) {
        max_result[index++] = upper;
        bs.set(upper);
      }
    }

    if ( index != max_result.length ) {
      return Arrays.copyOf(max_result, index);
    }
    return max_result;
  }
  private final IntervalSearchSet interval_set_;
}
